from typing import List

MAX_INT = 10 ** 4


class Solution:
    def minCost(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])

        def _is_valid(x, y):
            return 0 <= x < m and 0 <= y < n

        def neighbors(x1, y1):
            return [(x2, y2) for (x2, y2) in [(x1 - 1, y1), (x1 + 1, y1), (x1, y1 - 1), (x1, y1 + 1)]
                    if _is_valid(x2, y2)]

        dp = [[MAX_INT] * n for _ in range(m)]
        dp[0][0] = 0

        queue1 = [(0, 0)]
        while queue1:
            # 寻找当前花费能到达的所有路径（沿着当前箭头方向移动直至失效）
            visited = set(queue1)
            for i in range(len(queue1)):
                i1, j1 = queue1[i]
                v1 = dp[i1][j1]

                while True:
                    if grid[i1][j1] == 1:
                        j1 += 1
                    elif grid[i1][j1] == 2:
                        j1 -= 1
                    elif grid[i1][j1] == 3:
                        i1 += 1
                    else:
                        i1 -= 1

                    if 0 <= i1 < m and 0 <= j1 < n and (i1, j1) not in visited:
                        visited.add((i1, j1))
                        if v1 < dp[i1][j1]:
                            dp[i1][j1] = v1
                            queue1.append((i1, j1))
                    else:
                        break

            # 寻找当前花费所有路径修改1次能够到达的位置
            queue2 = []
            for i1, j1 in queue1:
                v1 = dp[i1][j1]
                for i2, j2 in neighbors(i1, j1):
                    if v1 + 1 < dp[i2][j2]:
                        dp[i2][j2] = v1 + 1
                        queue2.append((i2, j2))

            queue1 = queue2

        return dp[-1][-1]


if __name__ == "__main__":
    print(Solution().minCost(grid=[[1, 1, 1, 1], [2, 2, 2, 2], [1, 1, 1, 1], [2, 2, 2, 2]]))  # 3
    print(Solution().minCost(grid=[[1, 1, 3], [3, 2, 2], [1, 1, 4]]))  # 0
    print(Solution().minCost(grid=[[1, 2], [4, 3]]))  # 1
    print(Solution().minCost(grid=[[2, 2, 2], [2, 2, 2]]))  # 3
    print(Solution().minCost(grid=[[4]]))  # 0
